Search Results

Documents authored by Tóth, Géza

Document
DOI: 10.4230/LIPIcs.SoCG.2022.56
Disjointness Graphs of Short Polygonal Chains

Authors: János Pach, Gábor Tardos, and Géza Tóth

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
The disjointness graph of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph G of any system of segments in the plane is χ-bounded, that is, its chromatic number χ(G) is upper bounded by a function of its clique number ω(G). Here we show that this statement does not remain true for systems of polygonal chains of length 2. We also construct systems of polygonal chains of length 3 such that their disjointness graphs have arbitrarily large girth and chromatic number. In the opposite direction, we show that the class of disjointness graphs of (possibly self-intersecting) 2-way infinite polygonal chains of length 3 is χ-bounded: for every such graph G, we have χ(G) ≤ (ω(G))³+ω(G).
Cite as

János Pach, Gábor Tardos, and Géza Tóth. Disjointness Graphs of Short Polygonal Chains. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 56:1-56:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{pach_et_al:LIPIcs.SoCG.2022.56,
  author =	{Pach, J\'{a}nos and Tardos, G\'{a}bor and T\'{o}th, G\'{e}za},
  title =	{{Disjointness Graphs of Short Polygonal Chains}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{56:1--56:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.56},
  URN =		{urn:nbn:de:0030-drops-160645},
  doi =		{10.4230/LIPIcs.SoCG.2022.56},
  annote =	{Keywords: chi-bounded, disjointness graph}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.65
A Crossing Lemma for Multigraphs

Authors: János Pach and Géza Tóth

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Let G be a drawing of a graph with n vertices and e>4n edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton, the number of crossings in G is at least c{e^3 over n^2}, for a suitable constant c>0. In a seminal paper, Székely generalized this result to multigraphs, establishing the lower bound c{e^3 over mn^2}, where m denotes the maximum multiplicity of an edge in G. We get rid of the dependence on m by showing that, as in the original Crossing Lemma, the number of crossings is at least c'{e^3 over n^2} for some c'>0, provided that the "lens" enclosed by every pair of parallel edges in G contains at least one vertex. This settles a conjecture of Bekos, Kaufmann, and Raftopoulou.
Cite as

János Pach and Géza Tóth. A Crossing Lemma for Multigraphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{pach_et_al:LIPIcs.SoCG.2018.65,
  author =	{Pach, J\'{a}nos and T\'{o}th, G\'{e}za},
  title =	{{A Crossing Lemma for Multigraphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{65:1--65:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.65},
  URN =		{urn:nbn:de:0030-drops-87781},
  doi =		{10.4230/LIPIcs.SoCG.2018.65},
  annote =	{Keywords: crossing number, Crossing Lemma, multigraph, separator theorem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.59
Disjointness Graphs of Segments

Authors: János Pach, Gábor Tardos, and Géza Tóth

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
The disjointness graph G=G(S) of a set of segments S in R^d, d>1 is a graph whose vertex set is S and two vertices are connected by an edge if and only if the corresponding segments are disjoint. We prove that the chromatic number of G satisfies chi(G)<=omega(G)^4+omega(G)^3 where omega(G) denotes the clique number of G. It follows, that S has at least cn^{1/5} pairwise intersecting or pairwise disjoint elements. Stronger bounds are established for lines in space, instead of segments. We show that computing omega(G) and chi(G) for disjointness graphs of lines in space are NP-hard tasks. However, we can design efficient algorithms to compute proper colorings of G in which the number of colors satisfies the above upper bounds. One cannot expect similar results for sets of continuous arcs, instead of segments, even in the plane. We construct families of arcs whose disjointness graphs are triangle-free (omega(G)=2), but whose chromatic numbers are arbitrarily large.
Cite as

János Pach, Gábor Tardos, and Géza Tóth. Disjointness Graphs of Segments. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{pach_et_al:LIPIcs.SoCG.2017.59,
  author =	{Pach, J\'{a}nos and Tardos, G\'{a}bor and T\'{o}th, G\'{e}za},
  title =	{{Disjointness Graphs of Segments}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{59:1--59:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.59},
  URN =		{urn:nbn:de:0030-drops-71960},
  doi =		{10.4230/LIPIcs.SoCG.2017.59},
  annote =	{Keywords: disjointness graph, chromatic number, clique number, chi-bounded}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact